package com.ljy.my_study.leetcode.判断子序列;

/**
 * @author lijunying
 * @date 2020/7/27 17:04
 */
public class TestMain {

//    给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
//
//    你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
//
//    字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
//
//    示例 1:
//    s = "abc", t = "ahbgdc"
//
//    返回 true.
//
//    示例 2:
//    s = "axc", t = "ahbgdc"
//
//    返回 false.
//
//    后续挑战 :
//
//    如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

    public static void main(String[] args) {
//        String s="abc";
//        String t="ahbgdc";
//        System.out.println(new TestMain().isSubsequence(s,t));
        String s="1";
        String t="";
        System.out.println(new TestMain().isSubsequence(s,t));
        System.out.println(new TestMain().isSubsequence2(s,t));
        s="abc";
        t="acbdc";
        System.out.println(new TestMain().isSubsequence(s,t));
        System.out.println(new TestMain().isSubsequence2(s,t));
    }

    public boolean isSubsequence(String s, String t) {
        if(s==null||t==null){
            return false;
        }
        boolean[][] arr=new boolean[t.length()+1][s.length()+1];
        arr[0][0]=true;
        for(int i=1;i<arr.length;i++){
            arr[i][0]=true;
            for(int j=1;j<arr[0].length;j++){
                arr[i][j]=arr[i-1][j]||(arr[i-1][j-1]&&t.charAt(i-1)==s.charAt(j-1));
            }
        }
        return arr[t.length()][s.length()];
    }

//       a h b c d c
//       1 2 3 4 5 6
//   a 1 1 1 1 1 1 1
//   b 2 0 0 1 1 1 1
//   c 3 0 0 0 1 1 1

    public boolean isSubsequence2(String s, String t) {
        Boolean[][] array=new Boolean[s.length()+1][t.length()+1];
        array[0][0]=true;
        for(int i=0;i<array[0].length;i++){
            array[0][i]=true;
        }
        for(int i=1;i<array.length;i++){
            array[i][0]=false;
        }
        for(int i=1;i<array.length;i++){
            for(int j=1;j<array[i].length;j++){
                if(array[i][j-1]==true){
                    array[i][j]=true;
                }else if(array[i-1][j]==true&&s.charAt(i-1)==t.charAt(j-1)){
                    array[i][j]=true;
                }else{
                    array[i][j]=false;
                }
            }
        }
        return array[s.length()][t.length()];
    }
}
